Linear programming

LP

Primal (P), where x∈ℝnx \in \mathbb{R}^n: minimizecTxsubject toAx=bx≥0\begin{equation} \begin{aligned} & \text{minimize} & & c^T x \\ & \text{subject to} & & Ax = b \\ & & & x \geq 0 \end{aligned} \end{equation}

Lagrangian: L(x,λ,ν)=cTx−λTx+νT(Ax−b)=(c−λ+ATν)x−bTνL(x,\lambda,\nu)=c^T x - \lambda^T x + \nu^T (Ax-b) = (c-\lambda+A^T \nu)x-b^T \nu

Lagrange dual function (LDF): g(λ,ν)=infxL(x,λ,ν)={−bTνif c−λ+ATν=0−∞otherwiseg(\lambda,\nu) = \inf_x L(x,\lambda,\nu)=\begin{cases} -b^T \nu \quad \text{if } c-\lambda + A^T \nu = 0 \\ -\infty \quad \text{otherwise}\end{cases}

Lagrange dual problem (LDP): supλ≥0g(λ,ν)≡\sup_{\lambda \geq 0} g(\lambda,\nu) \equiv maxbTysubject toATy+λ=cλ≥0\begin{equation} \begin{aligned} & \max & & b^T y \\ & \text{subject to} & & A^T y + \lambda = c \\ & & & \lambda \geq 0 \end{aligned} \end{equation} where λ\lambda is the dual slack variable, transforming ATy≤cA^T y \leq c into an equality.

Dual (D): maxbTysubject toATy≤c\begin{equation} \begin{aligned} & \max & & b^T y \\ & \text{subject to} & & A^T y \leq c \end{aligned} \end{equation}

References:

  1. https://www.cs.princeton.edu/courses/archive/fall18/cos521/Lectures/lec17.pdf